#include<vector>
#include<algorithm>
using std::max;
using std::min;
using std::vector;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int dpMax = nums[0], dpMin = nums[0];
        int newMax, newMin;
        int maxProd = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            newMax = max(max(dpMax*nums[i], dpMin*nums[i]), nums[i]);
            newMin = min(min(dpMax*nums[i], dpMin*nums[i]), nums[i]);
            maxProd = max(maxProd, newMax);
            dpMax = newMax;
            dpMin = newMin;
        }
        return maxProd;

    }
};